'''
https://leetcode.cn/problems/reverse-nodes-in-k-group/
'''
from typing import Optional

from c03_list.utils import ListNode, generate_list, print_list


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverse(head):
            prev = None
            for _ in range(k):
                next = head.next
                head.next = prev
                prev = head
                head = next

        # 当前头，完成后的尾巴    当前的尾巴，完成后的头    下一个组开始的头
        cur_head_or_new_tail, cur_tail_or_new_head, next_head = head, None, head
        for _ in range(k):
            if not next_head: return head     # 不足k个直接返回
            cur_tail_or_new_head = next_head
            next_head = next_head.next

        reverse(head)
        # 新的尾巴，要连接下一组反转后的头
        cur_head_or_new_tail.next = self.reverseKGroup(next_head, k)
        return cur_tail_or_new_head

    def reverseKGroup_force_solution(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        list = []
        while head:
            list.append(head)
            head = head.next
        n = len(list)
        for i in range(0, n, k):
            a, b = i, i + k - 1
            if b >= n: break
            while a < b:
                list[a], list[b] = list[b], list[a]
                a, b = a + 1, b - 1
        watch_dog = ListNode()
        cur = watch_dog
        for node in list:
            cur.next = node
            cur = cur.next
        return watch_dog.next


arr = [1,2,3,4,5]
k = 2
list = generate_list(arr)
r = Solution().reverseKGroup(list, k)
print_list(r)